<?php
/**
 * https://leetcode.cn/problems/string-matching-in-an-array/
 * 数组中的字符串匹配
 * 给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
 * 如果你可以删除 words[j]最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
 * 示例
 * 输入：words = ["mass","as","hero","superhero"]
 * 输出：["as","hero"]
 * 解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
 * ["hero","as"] 也是有效的答案。
 */

namespace Xxb\XxbPhpAlgo\Topic;

class MatchSubString
{
    /**
     * @param String[] $words
     * @return String[]
     */
    function stringMatching($words)
    {
        $result = []; // [子字符串 => 1]
        foreach ($words as $word) {
            foreach ($words as $iWord) {
                if ($word == $iWord) {
                    continue;
                }
                if (isset($result[$iWord])) {
                    continue;
                }
                $head = 0;
                $tail = strlen($word) - 1;
                $subStrLen = strlen($iWord);
                while ($head <= $tail) {
                    if (substr($word, $head, $subStrLen) == $iWord) {
                        $result[$iWord] = 1;
                        break;
                    } else {
                        $head++;
                    }
                    if (substr($word, $tail - $subStrLen + 1, $subStrLen) == $iWord) {
                        $result[$iWord] = 1;
                        break;
                    } else {
                        $tail--;
                    }
                }
            }
        }
        return array_keys($result);
    }
}
